The present invention relates to a method and apparatus for using neural computing techniques, also known as neural networks, to optimize route selection in a computer communication network. The invention is particularly suitable for use with ATM networks, but can be used in other networks with Quality of Service requirements, such as IP and the OSI family of protocols.
The following acronyms are used:
ABRxe2x80x94Available Bit Rate
ARBPxe2x80x94Autoregressive Backpropagation
ARIMAxe2x80x94Autoregressive Integrated Moving Average
ARMAxe2x80x94Autoregressive Moving Average
ATMxe2x80x94Asynchronous Transfer Mode
B-ISDNxe2x80x94Broadband Integrated Services Digital Network
CACxe2x80x94Connection Admission Control
CBRxe2x80x94Constant Bit Rate
CDVxe2x80x94Cell Delay Variation
IBTxe2x80x94Intrinsic Burst Tolerance
IPxe2x80x94Internet Protocol
NNIxe2x80x94Network-to-Network Interface
OSIxe2x80x94Open Systems Interconnection
PCRxe2x80x94Peak Cell Rate
PVCxe2x80x94Permanent Virtual Circuit
QoSxe2x80x94Quality of Service
SCRxe2x80x94Sustainable Cell Rate
SVCxe2x80x94Switched Virtual Circuit
TCPxe2x80x94Transmission Control Protocol
UBRxe2x80x94Unspecified Bit Rate
UNIxe2x80x94User-to-Network Interface
UPCxe2x80x94Usage Parameter Control
VBRxe2x80x94Variable Bit Rate
Computer networks continue to carry increasing amounts of data traffic for various purposes. For example, the popularity of the Internet for educational, business and entertainment purposes is rapidly increasing. Moreover, local area networks, metropolitan area networks, and wide area networks have also become increasingly popular for use by corporations, the government, universities and the like. Furthermore, integration of networks that carry audio, video and other data is occurring.
Accordingly, different data transmission protocols have been developed in an attempt to manage the flow of data in these networks to avoid congestion and increase system throughput.
In particular, the ATM protocol is designed to provide a high-speed, low-delay multiplexing and switching network that supports any type of user traffic, such as voice, data, or video applications. ATM is an underlying technology for B-ISDN, which can offer video on demand, live television from multiple sources, full motion multimedia electronic mail, digital music, LAN interconnection, high-speed data transport for science and industry, and other services via an optical fiber telephone line.
Since ATM is a connection-oriented protocol, a virtual circuit is established prior to sending data. The virtual circuit defines the travel path for the data, e.g., which switches and transmission links are to be traversed. User traffic is segmented into small, fixed-length cells of 53 bytes each with cell headers that identify the virtual circuit. During transmission, high-speed switches read the cell header to relay the traffic to the next designated destination.
To optimize network resources and control congestion, various factors must be considered in selecting a virtual circuit. For example, an ATM network is required to perform a set of actions called Connection Admission Control (CAC) during a call setup to determine if a user connection will be accepted or rejected. However, traffic management through CAC offers a significant challenge to the designer. Complexity arises from the need to support the natural bit rates of all multi-application traffic being serviced in different consumer classes (e.g., CBR, UBR, VBR and ABR) through optimal sharing of bandwidth.
Additionally, various QoS parameters must be met. These parameters relate to cell error ratio, severely-errored cell block ratio, cell loss ratio, cell mis-insertion rate, cell transfer delay, mean cell transfer delay, and cell delay variation, for example.
Accordingly, an appropriate routing technique must be used to select an optimum virtual circuit and manage network traffic. Conventional routing techniques include nonadaptive algorithms (e.g., static routing) that do not base their routing decisions on real-time measurements or estimates of the current traffic and topology. The optimal route can therefore be computed in advance, off-line, and downloaded to the appropriate routers.
Static techniques includes shortest path routing, flooding, and flow-based routing.
In contrast, adaptive or dynamic routing algorithms change their routing decisions real-time to reflect changes in the topology and/or traffic. Dynamic routing techniques include distance vector routing and link state routing.
With the shortest path routing technique for selecting a virtual circuit, the shortest physical path between the source machine and the destination machine is selected. The routing decision is generally made once when a virtual circuit is being set up, and maintained for the remainder of the session. However, using shortest path routing on a per-request basis often leads to sub-optimal or even highly congested network solutions, and is not considered a good design practice.
Generally, in any given ATM network, the links with varying amounts of bandwidth can support a multitude of services using both point-to-point and point-to-multipoint routing mechanisms. Each of these services, when multiplexed over a common stream, needs optimal allocation of network resources based on global information across the entire network. From a network provider perspective, the routing strategy can be planned in a number of different ways to maximize revenue generation.
The present invention is concerned with finding an optimal routing solution that ensures minimum cost of routing with maximum bandwidth usage, while maintaining the QoS parameters within the user-specified threshold values.
Unlike conventional source (e.g., static) routing or dynamic routing schemes, the route discovery engine of the present invention constantly changes its decision based on the current traffic profile across all the links in the network. The engine uses a priori knowledge of the traffic pattern so that the decisions can be made in a real-time system without any significant delay.
Some researchers have tried to address this type of time-series prediction problem through expert systems. Their biggest drawback is the inflexibility caused by static, rule-based algorithms that require a priori knowledge of the system dynamics, and the need for human expertise to improve their performance. Moreover, statistical interpolation methods (e.g., using ARMA/ARIMA models) have limited success in certain situations, but the underlying assumption of linear system dynamics renders the model ineffective in most cases involving complex traffic patterns, which are highly non-linear.
The present invention is concerned with addressing the above issues by adapting an artificial neural network-based learning and prediction strategy to provide optimal routing selection and traffic management in a communication network.
Research efforts to date have produced various neural network-based approaches for parameter estimation and trend analysis of dynamic systems. The majority of these methods are based on state feedback, an approach limited by the availability of system states. However, in a typical communication network, such as an ATM network, the states are difficult to measure without employing elaborate, model-dependent state estimators and sensing devices. This makes the implementation of the traffic prediction algorithms based on state feedback very difficult.
These drawbacks have motivated the present research towards development of a neural network-based prediction scheme that makes use of only output measurements as they become available from sensor readings.
The Backpropagation Algorithm is a known neural network learning technique that looks for the minimum of an error function in weight space using the method of gradient descent. The combination of weights which minimizes the error function is considered to be a solution of the learning problem. However, ordinary backpropagation networks are unable to learn temporal and context sensitive patterns.
Accordingly, it would be desirable to provide a neural network-based prediction scheme employing a variant of the backpropagation network that makes use of only output measurements of a network to provide optimal routing selection and traffic management in a communication network.
The present invention provides a system having the above and other advantages.
The present invention relates to a method and apparatus for a neural network-based prediction scheme that makes use of only output measurements of a network to provide optimal routing selection and traffic management in a communication network.
A method is presented for determining an optimal route for transmission of data in a communication network that has several nodes interconnected by associated links. The method comprises the steps of: monitoring data traffic of at least particular ones of the links to obtain respective traffic histories thereof. The traffic may refer to a data rate such as bits/sec or cells/sec, for example. The monitoring may occur over a period of time such as hours, days, or weeks, for example. Next, a neural network is trained using the traffic histories to obtain respective predicted traffic profiles of the particular links.
The respective predicted traffic profiles are provided to a route discovery engine, along with topology information of the communication network. The route discovery engine processes the respective predicted traffic profiles and topology information. along with service request data, to select particular links for communicating data in the communication network.
Essentially, links are selected to provide a path with the lowest xe2x80x9ccostxe2x80x9d that also meets minimum feasibility requirements such as bandwidth and quality of service.
The topology information may include node/link names, available link capacity, cell processing time, cost of routing, and so forth.
Information indicative of the selected link(s) is communicated to particular node(s) associated with the links. Typically, the nodes are routers, in which case the information is communicated as routing table update information. The updated table information is stored at the router and accessed to determine the appropriate output link for each packet or cell received by the router on an input link.
The respective predicted traffic profiles may account for notified exceptions and logical exceptions. These are user-selected conditions for adjusting the selected path based on unusual situations such as links and nodes under repair, or expected unusually high or low traffic conditions.
Selection of the particular link(s) in the optimal communication path may be achieved by applying a shortest-path algorithm at the route discovery engine to the input parameters, e.g., the respective predicted traffic profiles, topology information, and service request data.
The neural network is preferably an autoregressive backpropagation network, in which case the method includes the further steps of determining respective feedback weights and feedforward weights for at least particular ones of the nodes; iteratively updating the respective feedback and feedforward weights to minimize an output error of the neural network; and selecting particular links for communicating data according to the respective updated feedforward and feedback weights.
The links may be selected at a user-to-network interface or network-to-network interface.
The method may include the further steps of providing a plurality of candidate routes comprising the links for communicating data in the communication network; providing a set of xe2x80x9cnxe2x80x9d network parameters (c1, . . . , cn) for each of the candidate routes; calculating a cost function for each of the candidate routes according to a weighted sum of the network parameters thereof; and selecting one of the candidate routes according to the associated cost function for communicating data in the communication network.
For example, the network parameters may include some or all of: link cost, peak cell rate, sustainable cell rate, intrinsic burst tolerance, cell delay variation, maximum allocated cell delay variation tolerance, cell loss ratio, and route length.
Additionally, limits may be provided for at least some of the network parameters for each of the candidate routes. For example, the link cost may be required to be in a certain range for a route to be acceptable. A determination is made as to whether the network parameters are within the associated limit; and one of the candidate routes is selected according to whether the network parameters thereof are within the associated limits.
The data traffic is preferably transmitted in the communication network using Asynchronous Transfer Mode (ATM).
An apparatus in accordance with the present invention includes a route discovery engine, a monitoring facility, and a neural network associated with the route discovery engine and the monitoring facility. The monitoring facility monitors data traffic of one or more of the links of a communication network to obtain respective traffic histories, and provides a corresponding signal to the neural network. The neural network receives this signal and calculates respective predicted traffic profiles of the particular links, and provides a corresponding signal to the route discovery engine. The route discovery engine receives the signal from the neural network and a signal indicative of a topology of the communication network, and selects different links for communicating data in the communication network.
The neural network receives a signal indicative of at least one of user-designated (a) notified exceptions and (b) logical exceptions for use in calculating the respective predicted traffic profiles.
The route discovery engine applies a shortest-path algorithm to select the particular link(s).
A transmitter associated with the route discovery engine transmits information indicative of the selected links(s) to particular node(s) associated with the links.
A routing table update function associated with the route discovery engine may be provided for communicating routing table update information indicative of the selected link(s) to the associated node(s).
When the neural network is an autoregressive backpropagation network, the neural network includes a processor for determining respective feedback weights and feedforward weights for the nodes, and for iteratively updating the respective feedback weights and feedforward weights to minimize an output error of the neural network.
Moreover, the route discovery engine evaluates a plurality of candidate routes comprising (e.g., traversing) the links for communicating data in the communication network according to a set of xe2x80x9cnxe2x80x9d network parameters (c1, . . . , cn) for each of the candidate routes. The route discovery engine includes a processor adapted to calculate a cost function for each of the candidate routes according to a weighted sum of the network parameters thereof; wherein the route discovery engine selects one of the candidate routes according to the associated cost function for communicating data in the communication network.
The route discovery engine may be responsive to limits for at least some of the network parameters for each of the candidate routes, in which case the route discovery engine includes a processor adapted to determine whether the network parameters are within the associated limit; where the route discovery engine is adapted to select one of the candidate routes according to whether the network parameters thereof are within the associated limits.